﻿using System;
using System.Collections.Generic;

namespace Chenglin.WPChildrenDrug.Models
{
    public class TrieTree
    {
        internal TrieNode root = new TrieNode(null);

        public TrieNode Insert(string s)
        {
            if (string.IsNullOrEmpty(s))
            {
                throw new ArgumentNullException("s");
            }

            TrieNode node = root;
            foreach (char c in s)
            {
                node = node.AddChild(c);
            }

            return node;
        }

        public void AddIndex(TrieNode node, int index)
        {
            if (node == null || node.Indexes.Contains(index))
                return;

            // Add the index to the current node
            node.Indexes.Add(index);

            // Add the index to its parent recursively (exclude the root)
            if (node.Parent.Parent != null)
            {
                AddIndex(node.Parent, index);
            }
        }

        /// <summary>
        /// Make the indexes sorted on every node. So that the latter search will be very efficient.
        /// </summary>
        public void SortIndexes()
        {
            root.SortIndexes();
        }

        public bool Contains(string s)
        {
            TrieNode node = Find(s);
            return node != null;
        }

        public TrieNode Find(string s)
        {
            if (string.IsNullOrEmpty(s))
            {
                throw new ArgumentNullException("s");
            }

            return ContainsInternal(s);
        }

        private TrieNode ContainsInternal(string s)
        {
            TrieNode node = root;
            foreach (char c in s)
            {
                node = node.GetChild(c);
                if (node == null)
                {
                    break;
                }
            }

            return node;
        }

        private TrieNode Insert(char c, TrieNode node)
        {
            return node.AddChild(c);
        }
    }

    public class TrieNode
    {
        internal Dictionary<char, TrieNode> children;
        private List<int> indexes;
        private char c;
        private TrieNode parent;

        public List<int> Indexes
        {
            get { return indexes; }
        }

        public TrieNode Parent
        {
            get { return parent; }
        }

        public TrieNode(TrieNode parent)
        {
            this.parent = parent;
            children = new Dictionary<char, TrieNode>();
            indexes = new List<int>();
        }

        public bool ContainChildren(char c)
        {
            return children.ContainsKey(c);
        }

        public TrieNode GetChild(char c)
        {
            TrieNode child;
            if (children.TryGetValue(c, out child))
            {
                return child;
            }
            return null;
        }

        internal TrieNode AddChild(char c)
        {
            TrieNode child;
            if (!children.TryGetValue(c, out child))
            {
                child = new TrieNode(this);
                child.c = c;

                children.Add(c, child);
            }
            return child;
        }

        /// <summary>
        /// Make the indexes sorted. So that the latter search will be very efficient.
        /// </summary>
        internal void SortIndexes()
        {
            indexes.Sort();
            foreach (var kvp in children)
            {
                kvp.Value.SortIndexes();
            }
        }
    }
}
